package day4;

public class ch1 {

    public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
  }

  //160
  public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        ListNode a = headA;
        ListNode b = headB;
        int num = 0;

        while (a!=b && num<3){
            a=a.next;
            b=b.next;
            if(a==null){
                a = headB;
                num++;
            }
            if(b==null){
                b = headA;
                num++;
            }
        }
        if(num<3){
            return a;
        }else {
            return null;
        }
  }

  public ListNode reverseList(ListNode head) {

        ListNode node = head.next;
        head.next = null;
        while (node!=null){
            ListNode next = node.next;
            node.next = head;
            head = node;
            node = next;

        }
        return head;
    }


    public boolean hasCycle(ListNode head) {
        ListNode a = head;
        ListNode b = head;
        while (b.next!=null&&b!=null){
            a = a.next;
            b = b.next.next;
            if(a==b){
                return true;
            }
        }
        return false;

    }


    public boolean isPalindrome(ListNode head) {
        ListNode a = head;
        ListNode b = head;
        while (b.next!=null&&b.next.next!=null){
            a = a.next;
            b = b.next.next;
        }

        ListNode mid = a.next;
        ListNode node = fun(mid);
        ListNode h = head;
        while (node!=null){
            if(h.val!=node.val){
                return false;
            }
            node = node.next;
            h = h.next;
        }
        fun(mid);
        return true;


    }


    public ListNode fun(ListNode head){

        ListNode node = head.next;
        head.next = null;

        while (node!=null){
            ListNode next = node.next;
            node.next = head;
            head = node;
            node = next;
        }

        return head;

    }



}
